package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

/**
 * 235gn 236不同的是, 236不是二叉搜索树
 */
public class LowestCommonAncestor236 {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null ) return root;
        if (root.val == q.val || root.val == p.val) return root;
        if (find(root.left, p) && find(root.left, q)) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (find(root.right, p) && find(root.right, q)) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    private static boolean find(TreeNode left, TreeNode q) {
        if (left == null) return false;
        if (left.val == q.val) return true;

        return find(left.left, q) || find(left.right, q);
    }

    public static void main(String[] args) {

    }
}
